package BHeap;

public class BHTimpl<T extends Comparable<T>> implements BHT<T> {
	protected BHNode<T> head;

	public BHTimpl() {
		// *** (HEAD)
		// NIL - NIL - NIL
		// ****** |
		// ***** NIL
		head = new BHNode<T>();
		head.setParent(new BHNode<T>());
		head.setChild(new BHNode<T>());
		head.setSibling(new BHNode<T>());
	}

	@Override
	public void make_heap() {
		head = new BHNode<T>();
		head.setParent(new BHNode<T>());
		head.setChild(new BHNode<T>());
		head.setSibling(new BHNode<T>());
	}

	public BHNode<T> getHead() {
		return this.head;
	}

	public void setHead(BHNode<T> newHead) {
		if (newHead != null) {
			if (!newHead.isEmpty())
				this.head = newHead;
		}
	}

	public void setDataHead(T newHead) {
		this.head.data = newHead;
	}

	@Override
	public void insert(T data) {
		if (data != null) {
			if (search(data).isEmpty()) {
				BHTimpl<T> newBHT = new BHTimpl<T>();
				newBHT.setDataHead(data);
				union(newBHT);
			}
		}
	}

	@Override
	public BHNode<T> minimum() {
		BHNode<T> tempY = new BHNode<T>();
		BHNode<T> tempX = head;
		T min = head.data;
		if (!tempX.isEmpty()) {
			tempX = minimum(head, min);
			return tempX;
		}
		return tempY;
	}

	private BHNode<T> minimum(BHNode<T> node, T min) {
		if (node.getData().compareTo(min) < 0) {
			min = node.getData();
		}
		if (!node.child.isEmpty()) {
			BHNode<T> temp = minimum(node.child, min);
			if (!temp.isEmpty())
				min = temp.getData();
		}
		if (!node.sibling.isEmpty()) {
			BHNode<T> temp = minimum(node.sibling, min);
			if (!temp.isEmpty())
				min = temp.getData();
		}
		return search(min);
	}

	// errado!
	@Override
	public void extract_mim() {
		BHNode<T> min = minimum();
		BHNode<T> subHeap = min.child;
		min.parent.sibling = min.sibling;
		BHT<T> newHeap = new BHTimpl<T>();
		newHeap.setHead(subHeap);
		union(newHeap);
	}

	@Override
	public void union(BHT<T> heap) {
		merge_binomial_heap(heap);
		unionRecursive(head);
		reorganizeHeap(head);
	}

	private void unionRecursive(BHNode<T> node) {
		if (!node.sibling.isEmpty()) {
			if (node.degree == node.sibling.degree) {
				BHNode<T> tempX = node.sibling;
				BHNode<T> tempY = node.child;
				node.sibling = node.sibling.sibling;
				node.child = tempX;
				node.child.parent = node;
				node.child.sibling = tempY;
				node.setDegree(node.getDegree() + 1);
				unionRecursive(node);
			} else {
				unionRecursive(node.sibling);
			}
		}
	}

	private void reorganizeHeap(BHNode<T> node) {
		if (!node.sibling.isEmpty()) {
			if (node.degree > node.sibling.degree) {
				BHNode<T> tempX = node.sibling.sibling;
				BHNode<T> tempY = node.sibling;
				node.sibling.setSibling(node);
				node.setSibling(tempX);
				if (node.equals(getHead())) {
					setHead(tempY);
				} else {
					searchPrev(node.getData()).sibling = tempY;
				}
				reorganizeHeap(node);
			} else {
				reorganizeHeap(node.sibling);
			}
		}
	}

	@Override
	public void decrease_key(T xElement, T kElement) {
		if (kElement.compareTo(xElement) < 0) {
			BHNode<T> tempX = search(xElement);
			tempX.setData(kElement);
			BHNode<T> child = tempX;
			BHNode<T> parent = child.getParent();
			while (!parent.isEmpty()
					&& child.getData().compareTo(tempX.getData()) < 0) {
				exchange(child, parent);
				BHNode<T> tempP = parent.getParent();
				child = parent;
				parent = tempP;
			}
		}
	}

	private void exchange(BHNode<T> tempY, BHNode<T> tempZ) {
		T element = tempY.getData();
		tempY.setData(tempZ.getData());
		tempZ.setData(element);
		BHNode<T> node = tempY.getParent();
		tempY.setParent(tempZ.getParent());
		tempZ.setParent(node);
		node = tempY.getSibling();
		tempY.setSibling(tempZ.getSibling());
		tempZ.setSibling(node);
	}

	@Override
	public void delete(T element, T menorValor) {
		decrease_key(element, menorValor);
		extract_mim();
	}

	@Override
	public void merge_binomial_heap(BHT<T> heap) {
		if (heap != null) {
			if (this.head.isEmpty()) {
				this.head = heap.getHead();
				return;
			}
			merge_binomial_heap_recursive(this.head, heap.getHead());
		}
	}

	private void merge_binomial_heap_recursive(BHNode<T> node1, BHNode<T> node2) {
		if (node1.isEmpty() && !node2.isEmpty()) {
			// entao todo o resto de node2 se unirah de uma vez com a minha heap
			node1 = node2;
			return;
		}
		if (!node2.isEmpty()) {
			BHNode<T> tempX, tempY;
			tempX = node1.sibling;
			tempY = node2.sibling;
			if (node1.getDegree() <= node2.getDegree()) {
				node1.setSibling(node2);
				node2.setSibling(tempX);
			} else {

				node2.setSibling(node1);
				if (node1.equals(getHead())) {
					setHead(node2);
				} else {
					searchPrev(node1.getData()).sibling = node2;
				}
			}
			merge_binomial_heap_recursive(tempX, tempY);
		}
	}

	@Override
	public void binomial_link(BHNode<T> child, BHNode<T> parent) {
		child.setParent(parent);
		child.setSibling(parent.getChild());
		parent.setChild(child);
		parent.setDegree(parent.getDegree() + 1);
	}

	private BHNode<T> searchPrev(T element) {
		BHNode<T> nodeFound = new BHNode<T>(), temp = head;
		if (element != null) {
			if (!temp.isEmpty())
				nodeFound = searchRecursivePrev(temp, element);
		}
		return nodeFound;
	}

	private BHNode<T> searchRecursivePrev(BHNode<T> prev, T element) {
		BHNode<T> node = prev.sibling;
		if (node.getData().compareTo(element) == 0) {
			return prev;
		}
		if (!node.child.isEmpty()) {
			BHNode<T> temp = searchRecursive(node.child, element);
			if (!temp.isEmpty())
				return temp;
		}
		if (!node.sibling.isEmpty()) {
			BHNode<T> temp = searchRecursive(node.sibling, element);
			if (!temp.isEmpty())
				return temp;
		}
		return new BHNode<T>();
	}

	@Override
	public BHNode<T> search(T element) {
		BHNode<T> nodeFound = new BHNode<T>(), temp = head;
		if (element != null) {
			if (!temp.isEmpty())
				nodeFound = searchRecursive(temp, element);
		}
		return nodeFound;
	}

	/**
	 * o metodo percorre toda a heap no sentido ↓ → quando terminar de percorrer
	 * uma subArvore, se nao achar retorna NIL, se achar retorna o node e dentro
	 * dos ifs, ha outros ifs que vazem a recursao parar. Pode ser melhorado!
	 */

	public BHNode<T> searchRecursive(BHNode<T> node, T element) {
		if (node.getData().compareTo(element) == 0) {
			return node;
		}
		if (!node.child.isEmpty()) {
			BHNode<T> temp = searchRecursive(node.child, element);
			if (!temp.isEmpty())
				return temp;
		}
		if (!node.sibling.isEmpty()) {
			BHNode<T> temp = searchRecursive(node.sibling, element);
			if (!temp.isEmpty())
				return temp;
		}
		return new BHNode<T>();
	}
}